/**
 * 数独求解器
 * 使用DFS回溯算法求解数独
 */

// 检查在指定位置放置数字是否有效
function isValid(board, row, col, num) {
  // 检查行
  for (let x = 0; x < 9; x++) {
    if (board[row][x] === num) {
      return false;
    }
  }
  
  // 检查列
  for (let x = 0; x < 9; x++) {
    if (board[x][col] === num) {
      return false;
    }
  }
  
  // 检查3x3宫格
  const startRow = Math.floor(row / 3) * 3;
  const startCol = Math.floor(col / 3) * 3;
  
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      if (board[startRow + i][startCol + j] === num) {
        return false;
      }
    }
  }
  
  return true;
}

// 检查用户输入是否有效（排除自身位置）
function isValidUserInput(board, row, col, num) {
  // 检查行（排除当前位置）
  for (let x = 0; x < 9; x++) {
    if (x !== col && board[row][x] === num) {
      return false;
    }
  }
  
  // 检查列（排除当前位置）
  for (let x = 0; x < 9; x++) {
    if (x !== row && board[x][col] === num) {
      return false;
    }
  }
  
  // 检查3x3宫格（排除当前位置）
  const startRow = Math.floor(row / 3) * 3;
  const startCol = Math.floor(col / 3) * 3;
  
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      const checkRow = startRow + i;
      const checkCol = startCol + j;
      if (!(checkRow === row && checkCol === col) && board[checkRow][checkCol] === num) {
        return false;
      }
    }
  }
  
  return true;
}

// 查找下一个空格
function findEmptyCell(board) {
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        return [row, col];
      }
    }
  }
  return null;
}

// 同步求解数独（不带可视化）
function solveSudoku(board) {
  const emptyCell = findEmptyCell(board);
  
  // 没有空格了，检查是否真的解决了
  if (!emptyCell) {
    return isSolved(board);
  }
  
  const [row, col] = emptyCell;
  
  // 尝试填入1-9
  for (let num = 1; num <= 9; num++) {
    if (isValid(board, row, col, num)) {
      board[row][col] = num;
      
      // 递归求解
      if (solveSudoku(board)) {
        return true;
      }
      
      // 回溯
      board[row][col] = 0;
    }
  }
  
  return false;
}

// 异步求解数独（带可视化）
async function solveSudokuWithVisualization(board, callback, speed = 50, shouldStop = null) {
  return await solveHelper(board, callback, speed, shouldStop);
}

async function solveHelper(board, callback, speed, shouldStop) {
  // 检查是否需要终止
  if (shouldStop && shouldStop()) {
    return false;
  }

  const emptyCell = findEmptyCell(board);
  
  // 没有空格了，检查是否真的解决了
  if (!emptyCell) {
    // 验证整个棋盘是否有效
    if (isSolved(board)) {
      return true;
    }
    return false;
  }
  
  const [row, col] = emptyCell;
  
  // 尝试填入1-9
  for (let num = 1; num <= 9; num++) {
    // 再次检查是否需要终止
    if (shouldStop && shouldStop()) {
      return false;
    }

    if (isValid(board, row, col, num)) {
      board[row][col] = num;
      
      // 调用回调函数更新UI（前进）
      if (callback) {
        await callback({
          type: 'forward',
          row: row,
          col: col,
          value: num,
          board: board.map(r => [...r])
        });
        
        // 延迟以显示动画
        await sleep(speed);
      }
      
      // 递归求解
      if (await solveHelper(board, callback, speed, shouldStop)) {
        return true;
      }
      
      // 回溯
      board[row][col] = 0;
      
      // 调用回调函数更新UI（回溯）
      if (callback) {
        await callback({
          type: 'backtrack',
          row: row,
          col: col,
          value: 0,
          board: board.map(r => [...r])
        });
        
        // 回溯时延迟稍长
        await sleep(speed * 1.5);
      }
    }
  }
  
  return false;
}

// 延迟函数
function sleep(ms) {
  return new Promise(resolve => setTimeout(resolve, ms));
}

// 验证数独是否已解决
function isSolved(board) {
  // 检查是否还有空格
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      if (board[row][col] === 0) {
        return false;
      }
    }
  }
  
  // 检查所有行、列、宫格是否有效
  for (let i = 0; i < 9; i++) {
    if (!isValidRow(board, i) || !isValidCol(board, i) || !isValidBox(board, i)) {
      return false;
    }
  }
  
  return true;
}

// 检查行是否有效
function isValidRow(board, row) {
  const seen = new Set();
  for (let col = 0; col < 9; col++) {
    const num = board[row][col];
    if (num !== 0) {
      if (seen.has(num)) {
        return false;
      }
      seen.add(num);
    }
  }
  return true;
}

// 检查列是否有效
function isValidCol(board, col) {
  const seen = new Set();
  for (let row = 0; row < 9; row++) {
    const num = board[row][col];
    if (num !== 0) {
      if (seen.has(num)) {
        return false;
      }
      seen.add(num);
    }
  }
  return true;
}

// 检查3x3宫格是否有效
function isValidBox(board, boxIndex) {
  const seen = new Set();
  const startRow = Math.floor(boxIndex / 3) * 3;
  const startCol = (boxIndex % 3) * 3;
  
  for (let i = 0; i < 3; i++) {
    for (let j = 0; j < 3; j++) {
      const num = board[startRow + i][startCol + j];
      if (num !== 0) {
        if (seen.has(num)) {
          return false;
        }
        seen.add(num);
      }
    }
  }
  return true;
}

module.exports = {
  solveSudoku,
  solveSudokuWithVisualization,
  isValid,
  isValidUserInput,
  isSolved,
  findEmptyCell
};
